import java.util.*;

/**
 * Created by zhourh on 2018/8/1.
 * 给定一个N叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
 */
public class NAryTreeLevelOrderTraversal {


    public static void main(String[] args) {
        Node root = new Node();
        root.val = 1;
        Node node2 = new Node();
        node2.val = 2;
        Node node3 = new Node();
        node3.val = 3;
        Node node4 = new Node();
        node4.val = 4;
        Node node5 = new Node();
        node5.val = 5;
        Node node6 = new Node();
        node6.val = 6;
        List<Node> level2 = new ArrayList<>();
        level2.add(node2);
        level2.add(node3);
        level2.add(node4);
        root.children = level2;
        List<Node> level3 = new ArrayList<>();
        level3.add(node5);
        level3.add(node6);
        node3.children = level3;

        System.out.println(new NAryTreeLevelOrderTraversal().levelOrder(root));

    }

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();

        if (root == null) {
            return ans;
        }

        Deque<Node> vector = new ArrayDeque<>();
        Deque<Node> nextOrderVector = new ArrayDeque<>();
        vector.push(root);
        while (!vector.isEmpty()) {
            List<Integer> order = new ArrayList<>();
            while (!vector.isEmpty()) {
                Node node = vector.pop();
                order.add(node.val);
                if (node.children != null && !node.children.isEmpty()) {
                    nextOrderVector.addAll(node.children);
                }
            }

            ans.add(order);
            vector.addAll(nextOrderVector);
            nextOrderVector.clear();
        }

        return ans;

    }
}
